home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Graphics / Viewers / aa_m68k_Intel_Only / ToyViewer1.2 / Source / gifsave.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-12  |  12.0 KB  |  470 lines
  1. /*
  2.     gifsave.c
  3.  
  4.     gifsave.c is based on "ppmtogif" of Jef Poskanzer.
  5.     It is modified for ToyViewer.app by T. Ogihara. (1995)
  6. */
  7.  
  8. /* ppmtogif.c - read a portable pixmap and produce a GIF file
  9. **
  10. ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A
  11. ** Lempel-Zim compression based on "compress".
  12. **
  13. ** Copyright (C) 1989 by Jef Poskanzer.
  14. **
  15. ** Permission to use, copy, modify, and distribute this software and its
  16. ** documentation for any purpose and without fee is hereby granted, provided
  17. ** that the above copyright notice appear in all copies and that both that
  18. ** copyright notice and this permission notice appear in supporting
  19. ** documentation.  This software is provided "as is" without express or
  20. ** implied warranty.
  21. **
  22. ** The Graphics Interchange Format(c) is the Copyright property of
  23. ** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
  24. ** CompuServe Incorporated.
  25. */
  26.  
  27. #include "gif.h"
  28. #include "save.h"
  29.  
  30. #define MAXCOLORS 256
  31.  
  32. /*
  33.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  34.  */
  35. typedef int    code_int;
  36.  
  37. #ifdef SIGNED_COMPARE_SLOW
  38. typedef unsigned long int count_int;
  39. #else /*SIGNED_COMPARE_SLOW*/
  40. typedef long int    count_int;
  41. #endif /*SIGNED_COMPARE_SLOW*/
  42.  
  43. static int GIFNextPixel(void);
  44. static void compress( int init_bits, FILE* outfile );
  45. static void init_output(void);
  46. static void output( code_int code );
  47. static void cl_block( void );
  48. static void cl_hash( count_int hsize );
  49. static void char_out( int c );
  50. static void flush_char( void );
  51.  
  52. /*****************************************************************************
  53.  *
  54.  * GIFENCODE.C    - GIF Image compression interface
  55.  *
  56.  * GIFEncode( FName, commonInfo, colornum, palette )
  57.  *
  58.  *****************************************************************************/
  59.  
  60. static int Width, Height;
  61. static int BitsPerPixel;
  62.  
  63. /*
  64.  * Return the next pixel from the image
  65.  */
  66. static int GIFNextPixel(void)
  67. {
  68.     int r, g, b;
  69.  
  70.     if( getPixel(&r, &g, &b) < 0 )
  71.         return EOF;
  72.     return mapping(r, g, b);
  73. }
  74.  
  75.  
  76. void
  77. GIFEncode( FILE *fp, commonInfo *cinf, int colornum, paltype *palette )
  78. {
  79.     int Resolution, ColorMapSize, InitCodeSize;
  80.     int i, j, B;
  81.  
  82.     for (i = 1, B = 0x02; i < 8; i++, B <<= 1)
  83.         if (B >= colornum) break;
  84.     BitsPerPixel = i;
  85.     ColorMapSize = 1 << BitsPerPixel;
  86.     Width = cinf->width;
  87.     Height = cinf->height;
  88.     Resolution = BitsPerPixel;
  89.  
  90.     /* The initial code size */
  91.     InitCodeSize = ( BitsPerPixel <= 1 ) ? 2 : BitsPerPixel;
  92.  
  93.     /* Write the Magic header */
  94.     fwrite( "GIF87a", 1, 6, fp );
  95.  
  96.     /* Write out the screen width and height */
  97.     put_short( cinf->width, fp );
  98.     put_short( cinf->height, fp );
  99.  
  100.     /* Indicate that there is a global colour map */
  101.     B = 0x80;            /* Yes, there is a color map */
  102.     B |= (Resolution - 1) << 5;    /* OR in the resolution */
  103.     B |= (BitsPerPixel - 1);    /* OR in the Bits per Pixel */
  104.     fputc( B, fp );
  105.  
  106.     /* Write out the Background colour */
  107.     fputc( 0, fp );
  108.     fputc( 0, fp );    /* Byte of 0's (future expansion) */
  109.  
  110.     /* Write out the Global Colour Map */
  111.     for(i = 0; i < ColorMapSize; ++i ) {
  112.         unsigned char *p = palette[i];
  113.         for (j = 0; j < 3; j++)
  114.             fputc( p[j], fp );
  115.     }
  116.  
  117.     /* Write an Image separator */
  118.     fputc( ',', fp );
  119.  
  120.     /* Write the Image header */
  121.     put_short( 0, fp );    /* LeftOfs */
  122.     put_short( 0, fp );    /* TopOfs */
  123.     put_short( Width, fp );
  124.     put_short( Height, fp );
  125.     fputc( 0x00, fp ); /* No interlace */
  126.  
  127.     /* Write out the initial code size */
  128.     fputc( InitCodeSize, fp );
  129.  
  130.     /*
  131.      * Go and actually compress the data
  132.      */
  133.     compress( InitCodeSize+1, fp );
  134.  
  135.     /* Write out a Zero-length packet (to end the series) */
  136.     fputc( 0, fp );
  137.     /* Write the GIF file terminator */
  138.     fputc( ';', fp );
  139. }
  140.  
  141.  
  142. /***************************************************************************
  143.  *
  144.  *  GIFCOMPR.C    - GIF Image compression routines
  145.  *
  146.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  147.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  148.  *
  149.  ***************************************************************************/
  150.  
  151. /*
  152.  * General DEFINEs
  153.  */
  154.  
  155. #define BITS    12
  156. #define HSIZE    5003    /* 80% occupancy */
  157.  
  158. /*
  159.  *
  160.  * GIF Image compression - modified 'compress'
  161.  *
  162.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  163.  *
  164.  * By Authors:  Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  165.  *        Jim McKie        (decvax!mcvax!jim)
  166.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  167.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  168.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  169.  *        Joe Orost        (decvax!vax135!petsd!joe)
  170.  */
  171. #include <ctype.h>
  172.  
  173. static int n_bits;        /* number of bits/code */
  174. static int maxbits = BITS;    /* user settable max # bits/code */
  175. static code_int maxcode;    /* maximum code, given n_bits */
  176. static code_int maxmaxcode = (code_int)1 << BITS;
  177.                 /* should NEVER generate this code */
  178. #ifdef COMPATIBLE        /* But wrong! */
  179. # define MAXCODE(n_bits)    ((code_int) 1 << (n_bits) - 1)
  180. #else /*COMPATIBLE*/
  181. # define MAXCODE(n_bits)    (((code_int) 1 << (n_bits)) - 1)
  182. #endif /*COMPATIBLE*/
  183.  
  184. static count_int htab [HSIZE];
  185. static unsigned short codetab [HSIZE];
  186. #define HashTabOf(i)       htab[i]
  187. #define CodeTabOf(i)    codetab[i]
  188.  
  189. static code_int hsize = HSIZE;    /* for dynamic table sizing */
  190.  
  191. /*
  192.  * To save much memory, we overlay the table used by compress() with those
  193.  * used by decompress().  The tab_prefix table is the same size and type
  194.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  195.  * get this from the beginning of htab.  The output stack uses the rest
  196.  * of htab, and contains characters.  There is plenty of room for any
  197.  * possible stack (stack used to be 8000 characters).
  198.  */
  199.  
  200. #define tab_prefixof(i) CodeTabOf(i)
  201. #define tab_suffixof(i)    ((unsigned char *)(htab))[i]
  202. #define de_stack    ((unsigned char *)&tab_suffixof((code_int)1<<BITS))
  203.  
  204. static code_int free_ent = 0;    /* first unused entry */
  205.  
  206. /*
  207.  * block compression parameters -- after all codes are used up,
  208.  * and compression rate changes, start over.
  209.  */
  210. static int clear_flg = 0;
  211.  
  212. static int offset;
  213. static long int in_count = 1;    /* length of input */
  214. static long int out_count = 0;    /* # of codes output (for debugging) */
  215.  
  216. /*
  217.  * compress stdin to stdout
  218.  *
  219.  * Algorithm:  use open addressing double hashing (no chaining) on the
  220.  * prefix code / next character combination.  We do a variant of Knuth's
  221.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  222.  * secondary probe.  Here, the modular division first probe is gives way
  223.  * to a faster exclusive-or manipulation.  Also do block compression with
  224.  * an adaptive reset, whereby the code table is cleared when the compression
  225.  * ratio decreases, but after the table fills.  The variable-length output
  226.  * codes are re-sized at this point, and a special CLEAR code is generated
  227.  * for the decompressor.  Late addition:  construct the table according to
  228.  * file size for noticeable speed improvement on small files.  Please direct
  229.  * questions about this implementation to ames!jaw.
  230.  */
  231.  
  232. static int g_init_bits;
  233. static FILE* g_outfile;
  234.  
  235. static int ClearCode;
  236. static int EOFCode;
  237.  
  238. static void
  239. compress( int init_bits, FILE *outfile )
  240. {
  241.     long fcode;
  242.     code_int i /* = 0 */;
  243.     int c;
  244.     code_int ent;
  245.     code_int disp;
  246.     code_int hsize_reg;
  247.     int hshift;
  248.  
  249.     /*
  250.      * Set up the globals:    g_init_bits - initial number of bits
  251.      *                g_outfile   - pointer to output file
  252.      */
  253.     g_init_bits = init_bits;
  254.     g_outfile = outfile;
  255.  
  256.     /*
  257.      * Set up the necessary values
  258.      */
  259.     offset = 0;
  260.     out_count = 0;
  261.     clear_flg = 0;
  262.     in_count = 1;
  263.     maxcode = MAXCODE(n_bits = g_init_bits);
  264.  
  265.     ClearCode = (1 << (init_bits - 1));
  266.     EOFCode = ClearCode + 1;
  267.     free_ent = ClearCode + 2;
  268.  
  269.     init_output();    /* Set up the 'byte output' routine */
  270.  
  271.     ent = GIFNextPixel();
  272.  
  273.     hshift = 0;
  274.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  275.     ++hshift;
  276.     hshift = 8 - hshift;        /* set hash code range bound */
  277.  
  278.     hsize_reg = hsize;
  279.     cl_hash( (count_int) hsize_reg);    /* clear hash table */
  280.  
  281.     output( (code_int)ClearCode );
  282.  
  283.     while ( (c = GIFNextPixel()) != EOF ) {
  284.     ++in_count;
  285.  
  286.     fcode = (long) (((long) c << maxbits) + ent);
  287.     i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  288.  
  289.     if ( HashTabOf (i) == fcode ) {
  290.         ent = CodeTabOf (i);
  291.         continue;
  292.     } else if ( (long)HashTabOf (i) < 0 )    /* empty slot */
  293.         goto nomatch;
  294.     disp = hsize_reg - i;    /* secondary hash (after G. Knott) */
  295.     if ( i == 0 )
  296.         disp = 1;
  297. probe:
  298.     if ( (i -= disp) < 0 )
  299.         i += hsize_reg;
  300.  
  301.     if ( HashTabOf (i) == fcode ) {
  302.         ent = CodeTabOf (i);
  303.         continue;
  304.     }
  305.     if ( (long)HashTabOf (i) > 0 )
  306.         goto probe;
  307. nomatch:
  308.     output ( (code_int) ent );
  309.     ++out_count;
  310.     ent = c;
  311.     if ( free_ent < maxmaxcode ) {
  312.         CodeTabOf (i) = free_ent++; /* code -> hashtable */
  313.         HashTabOf (i) = fcode;
  314.     } else
  315.         cl_block();
  316.     }
  317.     /*
  318.      * Put out the final code.
  319.      */
  320.     output( (code_int)ent );
  321.     ++out_count;
  322.     output( (code_int) EOFCode );
  323. }
  324.  
  325. /*****************************************************************
  326.  * Output the given code.
  327.  * Inputs:
  328.  *      code:    A n_bits-bit integer.  If == -1, then EOF.
  329.  *        This assumes that n_bits =< (long)wordsize - 1.
  330.  * Outputs:
  331.  *      Outputs code to the file.
  332.  * Assumptions:
  333.  *      Chars are 8 bits long.
  334.  * Algorithm:
  335.  *      Maintain a BITS character long buffer (so that 8 codes will
  336.  * fit in it exactly).  Use the VAX insv instruction to insert each
  337.  * code in turn.  When the buffer fills up empty it and start over.
  338.  */
  339.  
  340. static unsigned long cur_accum = 0;
  341. static int cur_bits = 0;
  342.  
  343. static void output( code_int code )
  344. {
  345.     static unsigned long masks[] = {
  346.         0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  347.         0x001F, 0x003F, 0x007F, 0x00FF,
  348.         0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  349.         0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  350.  
  351.     if( cur_bits > 0 ) {
  352.         cur_accum &= masks[ cur_bits ];
  353.         cur_accum |= ((long)code << cur_bits);
  354.     }else
  355.         cur_accum = code;
  356.     cur_bits += n_bits;
  357.     while( cur_bits >= 8 ) {
  358.         char_out( (unsigned int)(cur_accum & 0xff) );
  359.         cur_accum >>= 8;
  360.         cur_bits -= 8;
  361.     }
  362.     /*
  363.      * If the next entry is going to be too big for the code size,
  364.      * then increase it, if possible.
  365.      */
  366.     if ( free_ent > maxcode || clear_flg ) {
  367.         if( clear_flg ) {
  368.             maxcode = MAXCODE (n_bits = g_init_bits);
  369.             clear_flg = 0;
  370.         } else {
  371.             ++n_bits;
  372.             maxcode = ( n_bits == maxbits )
  373.                 ? maxmaxcode : MAXCODE(n_bits);
  374.         }
  375.     }
  376.     if( code == EOFCode ) {
  377.         /* At EOF, write the rest of the buffer. */
  378.         while( cur_bits > 0 ) {
  379.             char_out( (unsigned int)(cur_accum & 0xff) );
  380.             cur_accum >>= 8;
  381.             cur_bits -= 8;
  382.         }
  383.         flush_char();
  384.         fflush( g_outfile );
  385.         /* if( ferror( g_outfile ) ) writeerr(); */
  386.     }
  387. }
  388.  
  389. /*
  390.  * Clear out the hash table
  391.  */
  392. static void cl_block(void)    /* table clear for block compress */
  393. {
  394.     cl_hash ( (count_int) hsize );
  395.     free_ent = ClearCode + 2;
  396.     clear_flg = 1;
  397.     output( (code_int)ClearCode );
  398. }
  399.  
  400. static void cl_hash(count_int hsize)    /* reset code table */
  401. {
  402.  
  403.     count_int *htab_p = htab+hsize;
  404.     long i;
  405.     long m1 = -1;
  406.  
  407.     i = hsize - 16;
  408.     do {        /* might use Sys V memset(3) here */
  409.         *(htab_p-16) = m1;
  410.         *(htab_p-15) = m1;
  411.         *(htab_p-14) = m1;
  412.         *(htab_p-13) = m1;
  413.         *(htab_p-12) = m1;
  414.         *(htab_p-11) = m1;
  415.         *(htab_p-10) = m1;
  416.         *(htab_p-9) = m1;
  417.         *(htab_p-8) = m1;
  418.         *(htab_p-7) = m1;
  419.         *(htab_p-6) = m1;
  420.         *(htab_p-5) = m1;
  421.         *(htab_p-4) = m1;
  422.         *(htab_p-3) = m1;
  423.         *(htab_p-2) = m1;
  424.         *(htab_p-1) = m1;
  425.         htab_p -= 16;
  426.     } while ((i -= 16) >= 0);
  427.  
  428.     for ( i += 16; i > 0; --i )
  429.         *--htab_p = m1;
  430. }
  431.  
  432. /****************************************************************************
  433.  *
  434.  * GIF Specific routines
  435.  *
  436.  ****************************************************************************/
  437.  
  438. static int a_count;    /* Number of characters so far in this 'packet' */
  439. static char accum[256];    /* Define the storage for the packet accumulator */
  440.  
  441. static void init_output(void)
  442. {
  443.     cur_accum = 0;
  444.     cur_bits = 0;
  445.     a_count = 0;
  446. }
  447.  
  448. /*
  449.  * Add a character to the end of the current packet, and if it is 254
  450.  * characters, flush the packet to disk.
  451.  */
  452. static void char_out( int c )
  453. {
  454.     accum[ a_count++ ] = c;
  455.     if( a_count >= 254 )
  456.         flush_char();
  457. }
  458.  
  459. /*
  460.  * Flush the packet to disk, and reset the accumulator
  461.  */
  462. static void flush_char( void )
  463. {
  464.     if( a_count > 0 ) {
  465.         fputc( a_count, g_outfile );
  466.         fwrite( accum, 1, a_count, g_outfile );
  467.         a_count = 0;
  468.     }
  469. }
  470.